#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MaxSize 100
typedef struct
{
    int data[MaxSize];	
    int top;			
} StType;				
int count=0;
int place(StType st,int i,int j)  
{
    int a=0;         
    int k=1;
    if (i==1)
    {
        a=1;
        return a;	
    }
    while (k<=i-1)			
    {
        if ((st.data[k]==j)||(fabs(j-st.data[k])==fabs(i-k)))
        {
            a=0;
            return a;
        }
        else
            k++;
    }
    a=1;
    return a;
}
void queen(int n)					
{
    int i,j,k;
    int find=0;
    StType st;						
    st.top=0;						
    st.top++;						
    st.data[st.top]=1;
    while (st.top>0)				
    {
        i=st.top;					
        if (st.top==n)				
        {
            printf("第%d个解：",++count);
            for (k=1; k<=st.top; k++)
                printf("(%d,%d) ",k,st.data[k]);
            printf("\n");
        }
        find=0;
        for (j=1; j<=n; j++)
            if (place(st,i+1,j))	/
            {
                st.top++;
                st.data[st.top]=j;
                find=1;
                break;
            }
        if (find==0)			
        {
            while (st.top>0)
            {
                if (st.data[st.top]==n)
                    st.top--;
                for (j=st.data[st.top]+1; j<=n; j++)	
                    if (place(st,st.top,j))
                    {
                        st.data[st.top]=j;
                        break;
                    }
                if (j>n)				
                    st.top--;			
                else					
                    break;
            }
        }
    }
}
 
int main()
{
    int n;
    printf(" 皇后问题(n<20) n=");
    scanf("%d",&n);
    printf(" %d皇后问题求解如下：\n",n);
    queen(n);
    printf("\n");
    return 0;
}